package com.gorkr.backtracking;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author gorkr
 * @date 2022/06/19 19:30
 **/
public class M698PartitionTokEqualSumSubsets {

    private HashMap<String,Boolean> memo = new HashMap<>();

    public boolean canPartitionKSubsets(int[] nums, int k) {

        int sum = 0;

        for (int num :
                nums) {
            sum += num;
        }

        if (sum % k != 0) {
            return false;
        }

        // 每个子集应有的和
        int target = sum / k;

        int[] resSet = new int[k];

        // 以数字为视角  么个数字考虑筒
//        return backTracking(nums, 0, target, resSet);

        // 以桶为视角 每个筒考虑数字
        return partition(0,nums,new boolean[nums.length],target,new int[k]);

    }

    /**
     * @param nums   第几个数字
     * @param i  第几个数字
     * @param target
     * @param resSet 同当前集合的值
     * @return
     */
    private boolean backTracking(int[] nums, int i, int target, int[] resSet) {

        // base case
        // todo : 验证最后诸多返回到底是哪个返回正确
        // 做完最后一个选择
        if (i == nums.length) {
            for (int res :
                    resSet) {
                if (res != target) {
                    return false;
                }
            }
            return true;
        }


        for (int j = 0; j < resSet.length; j++) {
            // 做选择  奥 必放桶其一
            resSet[j] += nums[i];
            if (backTracking(nums, i + 1, target, resSet)) {
                return true;
            }
            resSet[j] -= nums[i];
        }
        return false;
    }


    /**
     * @param k_index 同序号 递归用
     * @param nums    数字列表
     * @param used    是否已经如了一个筒
     * @param target  每个桶的目标值
     * @param resSet  每个桶当前总和
     * @return
     */
    private boolean partition(int k_index, int[] nums, boolean[] used, int target, int[] resSet) {


        String state = Arrays.toString(used);



        if(memo.containsKey(state)){
            return memo.get(state);
        }

        if(resSet[k_index]==target){
            k_index++;
//            memo.put(state,partition(k_index+1, nums, used,target, resSet ));

        }else if(resSet[k_index]>target){
            return false;
        }



        // 选择列表是数字 当前列表从数字里选择一个入筒
        for (int i = 0; i < nums.length; i++) {

            // 做选择
            if (!used[i]) {
                if (nums[i] + resSet[k_index]  > target) {
                    // 当前桶装不下 nums[i]
                    continue;
                }

                resSet[k_index] += nums[i];
                used[i] = true;

                if(partition(k_index, nums, used,target, resSet )){
                    return true;
                }
                resSet[k_index] -= nums[i];
                used[i] = false;

            }
            if(k_index==resSet.length){
                return true;
            }
        }


        return false;
    }

    @Test
    public void test() {
        int[] nums = {4, 3, 2, 3, 5, 2, 1};
        int k = 4;
        System.out.println(canPartitionKSubsets(nums, k));
    }


}
    